'''
https://leetcode.cn/problems/connecting-cities-with-minimum-cost
'''
from typing import List


class UF:
    def __init__(self, n):
        self.father = [i for i in range(n)]
    def find(self, x):
        if x != self.father[x]:
            self.father[x] = self.find(self.father[x])
        return self.father[x]
    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy: return False
        self.father[fy] = fx
        return True

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        uf = UF(n + 1)
        n_connected = 1
        total_cost = 0
        connections.sort(key = lambda x: x[2])
        for u, v, w in connections:
            if uf.union(u, v):
                n_connected += 1
                total_cost += w
            if n_connected == n:
                return total_cost
        return -1 if n_connected != n else total_cost
